package leetcode.动态规划.零一背包;

import java.util.HashMap;

public class Leetcode494 {
    //dfs
    public int findTargetSumWays(int[] nums, int S) {
        return dfs(nums,S,0);
    }

    public int dfs(int[] nums, int S,int index){
        if(index==nums.length){
            if(S==0){
                return 1;
            }else{
                return 0;
            }
        }
        int res = 0;
        int add = dfs(nums,S+nums[index],index+1);
        int sub = dfs(nums,S-nums[index],index+1);
        return res+add+sub;
    }
    //dfs+记忆化
    public int findTargetSumWays1(int[] nums, int S){
        HashMap<String, Integer> memo = new HashMap<>();
        return dfs(nums,S,0,memo);
    }

    public int dfs(int[] nums, int S,int index,HashMap<String, Integer> memo){
        if(index==nums.length){
            if(S==0){
                return 1;
            }else{
                return 0;
            }
        }
        int res = 0;
        String key = index + "," + S;
        if(memo.containsKey(key)){
            return memo.get(key);
        }

        int add = dfs(nums,S+nums[index],index+1,memo);
        int sub = dfs(nums,S-nums[index],index+1,memo);
        memo.put(key,res+add+sub);
        return res+add+sub;
    }
    //动态规划
    public int findTargetSumWays2(int[] nums, int S){
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if(S>sum){
            return 0;
        }
        if((S+sum)/2==1){
            return 0;
        }
        int target = (S+sum)/2;
        int[]dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for(int j = target;j>=nums[i];j--){
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}
